//
// Created by ASUS on 2024/4/20/星期六.
//
/*
 一般定义f[S][i] 表示已经排列好的元素（下标）集合为S，且上一个填的元素（下标）为i 时，
 和题目有关的最优值。通过枚举当前位置要填的元素来转移。
 */
#include <bits/stdc++.h>
using namespace std;


const int mod=1e9+7;

//lc2741,相邻两个数一个被另一个整除
int specialPerm(vector<int>& nums) {
	int n=nums.size();
	vector<vector<int>> memo(1<<n,vector<int>(n,-1));
	function<int(int,int)> dfs=[&](int mask,int j)->int{
		if(mask==0) return 1;
		if(memo[mask][j]!=-1) return memo[mask][j];
		long long res=0;
		for(int i=0;i<n;i++){
			if((mask>>i&1)&&(nums[i]%nums[j]==0||nums[j]%nums[i]==0)){
				res+=dfs(mask^(1<<i),i);
			}
		}
		return memo[mask][j]=res%mod;
	};
	long long ans=0;
	int u=(1<<n)-1;
	for(int i=0;i<n;i++){
		ans=(ans+dfs(u^(1<<i),i))%mod;
	}
	return ans;
}